/**
 * 
 */
package ro.dta.idbi.model.dynamicpattern;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import ro.dta.idbi.interfaces.IGraphHash;

/**
 * Implementation of the graph hash algorithm
 * 
 * @author Tudor Dobrila
 * 
 */
public class GraphHash implements IGraphHash {

	/**
	 * Hash algorithm used to hash the graph
	 */
	private MessageDigest digest;

	/**
	 * Hashtable of vertex coders
	 */
	private Map<VertexEdgePair, VertexCoder> coders;
	
	/**
	 * Total execution time
	 */
	private long totalTime;

	/**
	 * GraphHash class constructor
	 * 
	 * @param algorithm
	 *            Hash algorithm used to hash the graph (e.g. MD5)
	 * @throws NoSuchAlgorithmException
	 *             If the hash algorithm is not found
	 */
	public GraphHash(String algorithm) throws NoSuchAlgorithmException {
		this.digest = MessageDigest.getInstance(algorithm);
	}

	/* (non-Javadoc)
	 * @see ro.dta.idbi.model.dynamicpattern.IGraphHash#computeHash(int[][])
	 */
	@Override
	public String computeHash(int[][] adjacencyMatrix) {
		if (adjacencyMatrix.length == 0 || adjacencyMatrix.length != adjacencyMatrix[0].length) {
			throw new IllegalArgumentException("Invalid adjacency matrix");
		}

		long startTime = System.currentTimeMillis();
		
		// Convert from adjacency matrix
		int noVertices = adjacencyMatrix.length;
		Vertex[] vertices = new Vertex[noVertices];
		for (int i = 0; i < noVertices; i++) {
			int noOut = 0, noIn = 0;
			for (int j = 0; j < noVertices; j++) {
				if (adjacencyMatrix[i][j] != 0) {
					noOut++;
				}

				if (adjacencyMatrix[j][i] != 0) {
					noIn++;
				}
			}

			vertices[i] = new Vertex(i, noOut, noIn);
		}

		for (int i = 0; i < noVertices; i++) {
			for (int j = 0; j < noVertices; j++) {
				if (adjacencyMatrix[i][j] != 0) {
					Edge edge = new Edge(vertices[i], vertices[j]);
					vertices[i].addOutEdge(edge);
					vertices[j].addInEdge(edge);
				}
			}
		}

		coders = new HashMap<GraphHash.VertexEdgePair, GraphHash.VertexCoder>();

		// Construct root vertex coder and add its children, i.e. all vertices
		VertexCoder root = new VertexCoder();
		for (int i = 0; i < noVertices; i++) {
			VertexCoder child = new VertexCoder(vertices[i], null, root, 1);
			root.addChild(child);
		}
		root.computeHash();
		totalTime = System.currentTimeMillis() - startTime;
		
		return root.getCode();
	}

	/**
	 * Compute the hash of a string
	 * 
	 * @param message
	 *            String for which the hash needs to be computed
	 * @return Hash value of the string
	 */
	private String computeHash(String message) {
		digest.reset();
		digest.update(message.getBytes());

		byte messageDigest[] = digest.digest();
		StringBuffer hexString = new StringBuffer();
		for (int i = 0; i < messageDigest.length; i++) {
			hexString.append(Integer.toHexString(0xFF & messageDigest[i]));
		}

		return hexString.toString();
	}
	
	/* (non-Javadoc)
	 * @see ro.dta.idbi.model.dynamicpattern.IGraphHash#getTotalTime()
	 */
	@Override
	public long getTotalTime() {
		return totalTime;
	}

	/**
	 * Representation of a vertex coder
	 * 
	 * @author Tudor Dobrila
	 * 
	 */
	class VertexCoder {

		/**
		 * Vertex associated with the coder
		 */
		private Vertex vertex;

		/**
		 * Edge in the graph associated with the coder
		 */
		private Edge edge;

		/**
		 * Hash code of the vertex coder
		 */
		private String code;

		/**
		 * Parent vertex coder, that created this one
		 */
		private VertexCoder parent;

		/**
		 * Generation no. of the vertex coder
		 */
		private int generation;

		/**
		 * Child vertex coders, created by this vertex coder
		 */
		private List<VertexCoder> children;

		/**
		 * True if the vertex coder has been expanded, false otherwise
		 */
		private boolean expanded;

		/**
		 * VertexCoder empty constructor
		 */
		public VertexCoder() {
			this.generation = 0;
			this.children = new ArrayList<GraphHash.VertexCoder>();
		}

		/**
		 * VertexCoder class constructor
		 * 
		 * @param vertex
		 *            Vertex associated with the coder
		 * @param edge
		 *            Edge associated with the coder
		 * @param parent
		 *            Parent vertex coder, that created this coder
		 * @param generation
		 *            Generation no. of the vertex coder
		 */
		public VertexCoder(Vertex vertex, Edge edge, VertexCoder parent, int generation) {
			this();
			this.vertex = vertex;
			this.edge = edge;
			this.parent = parent;
			this.generation = generation;
		}

		/**
		 * Compute the hash of the vertex coder
		 */
		public void computeHash() {
			if (vertex == null) {
				// Root node
				for (int i = 0; i < children.size(); i++) {
					children.get(i).expand();
				}

				while (true) {
					for (int i = 0; i < children.size(); i++) {
						children.get(i).computeHash();
					}

					Collections.sort(children, new VertexCoderComparer());

					// Check if there are two children with the same hash code
					int i = 0;
					for (i = 0; i < children.size() - 1; i++) {
						if (!children.get(i).expanded
								&& children.get(i).getCode().equals(children.get(i + 1).getCode())) {
							break;
						}
					}

					if (i >= children.size() - 1) {
						// All children have been expanded
						break;
					}

					int j = i + 1;
					while (j < children.size()
							&& children.get(i).getCode().equals(children.get(j).getCode())) {
						children.get(j).expand();
						j++;
					}
				}
			}

			String oldCode = code;
			for (int i = 0; i < children.size(); i++) {
				children.get(i).computeHash();
			}
			Collections.sort(children, new VertexCoderComparer());

			String content = "";
			if (vertex != null && edge != null) {
				// Not the root
				if (edge.getSource() == vertex) {
					content = "0";
				} else {
					content = "1";
				}

			}

			for (int i = 0; i < children.size(); i++) {
				content += children.get(i).getCode();
			}

			code = GraphHash.this.computeHash(content);
			if (code.equals(oldCode)) {
				expanded = true;
			}
		}

		/**
		 * Expand the node one level down
		 */
		public void expand() {
			if (expanded) {
				return;
			}

			if (children.size() == 0) {
				for (int i = 0; i < vertex.getOutEdgeCount(); i++) {
					Edge crtEdge = vertex.getOutEdge(i);
					VertexEdgePair vePair = new VertexEdgePair(crtEdge.getTarget(), crtEdge);
					if (coders.containsKey(vePair)) {
						VertexCoder child = coders.get(vePair);
						if (child.generation == generation + 1) {
							children.add(child);
						}
					} else {
						VertexCoder child = new VertexCoder(crtEdge.getTarget(), crtEdge, this,
								generation + 1);
						children.add(child);
						coders.put(vePair, child);
					}
				}
			
				for (int i = 0; i < vertex.getInEdgeCount(); i++) {
					Edge crtEdge = vertex.getInEdge(i);
					VertexEdgePair vePair = new VertexEdgePair(crtEdge.getSource(), crtEdge);
					if (coders.containsKey(vePair)) {
						VertexCoder child = coders.get(vePair);
						if (child.generation == generation + 1) {
							children.add(child);
						}
					} else {
						VertexCoder child = new VertexCoder(crtEdge.getSource(), crtEdge, this,
								generation + 1);
						children.add(child);
						coders.put(vePair, child);
					}
				}
			} else {
				for (int i = 0; i < children.size(); i++) {
					if (children.get(i).parent == this) {
						children.get(i).expand();
					}
				}
			}
		}

		/**
		 * Add a child vertex coder to this coder
		 * 
		 * @param coder
		 *            Vertex coder to add as a child
		 */
		public void addChild(VertexCoder coder) {
			children.add(coder);
		}

		/**
		 * Get the hash code of this coder
		 * 
		 * @return Hash code of the coder
		 */
		public String getCode() {
			return code;
		}
	}

	/**
	 * Representation of a (vertex,edge) pair
	 * 
	 * @author Tudor Dobrila
	 * 
	 */
	static class VertexEdgePair implements Map.Entry<Vertex, Edge> {

		/**
		 * Vertex in the pair
		 */
		private Vertex vertex;

		/**
		 * Edge in the pair
		 */
		private Edge edge;

		/**
		 * VertexEdgePair class construcotr
		 * 
		 * @param vertex
		 *            Vertex in the pair
		 * @param edge
		 *            Edge in the pair
		 */
		public VertexEdgePair(Vertex vertex, Edge edge) {
			this.vertex = vertex;
			this.edge = edge;
		}

		@Override
		public Vertex getKey() {
			return vertex;
		}

		@Override
		public Edge getValue() {
			return edge;
		}

		@Override
		public Edge setValue(Edge value) {
			return null;
		}

	}

	/**
	 * Vertex coder comparer, used to compare two vertex coders
	 * 
	 * @author Tudor Dobrila
	 * 
	 */
	static class VertexCoderComparer implements Comparator<VertexCoder> {

		@Override
		public int compare(VertexCoder o1, VertexCoder o2) {
			// Compare the hash codes of the coders
			return o1.getCode().compareTo(o2.getCode());
		}

	}
}
